package com.zwj.interview.二叉树之使用两个队列;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 给定一棵二叉树，如果站在该二叉树的右侧，那么从上到下看到的节点构成二叉树的右侧视图
 */
public class 二叉树右侧视图列表III {

    /**
     * 当站在二叉树的右侧时，看到的应该是每层最右边的一个节点，
     * 而每层的其他节点都被最右边的节点挡住。因此，二叉树的右侧视图其实就是从上到下每层最右边的节点
     *
     * @param root
     * @return
     */
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> view = new LinkedList<>();
        if (root == null) {
            return view;
        }
        Queue<TreeNode> queue1 = new LinkedList<>();
        Queue<TreeNode> queue2 = new LinkedList<>();
        queue1.offer(root);
        /**
         * 变量node是当前遍历到的节点。当队列queue1被清空时（即queue1.isEmpty()为true时），
         * 当前这一层已经遍历完，变量node是这一层的最右边的节点，可以添加到右侧视图中。
         * 当从上到下所有层的节点都遍历完之后，二叉树的右侧视图的所有节点就都已经找到
         */
        while (!queue1.isEmpty()) {
            TreeNode node = queue1.poll();
            if (node.left != null) {
                queue2.offer(node.left);
            }
            if (node.right != null) {
                queue2.offer(node.right);
            }
            if (queue1.isEmpty()) {
                view.add(node.val);
                queue1 = queue2;
                queue2 = new LinkedList<>();
            }
        }
        return view;
    }

    public List<Integer> rightSideView2(TreeNode root) {
        List<Integer> result=new ArrayList<>();
        if(root==null){
           return result;
        }
        Queue<TreeNode> queue1=new LinkedList<>();
        Queue<TreeNode> queue2=new LinkedList<>();
        queue1.add(root);
        while(!queue1.isEmpty()){
            TreeNode cur=queue1.poll();
            if(cur.left!=null){
                queue2.offer(cur.left);
            }
            if(cur.right!=null){
                queue2.offer(cur.right);
            }
            if(queue1.isEmpty()){
                result.add(cur.val);
                queue1=queue2;
                queue2=new LinkedList<>();
            }
        }
        return result;
    }



}
